#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <utility>
using namespace std;

typedef struct TreeNode
{
    int val;
    struct TreeNode *right;
    struct TreeNode *left;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
} TreeNode;

// 二叉树的锯齿形层序遍历
class Solution1
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        if (root == nullptr)
            return {};

        // 根节点入队列
        queue<TreeNode *> q;
        q.emplace(root);
        vector<vector<int>> ret;

        int currentFloorSize = 0;
        int flag = 1; // 遍历层的方向,奇数层left->right, 偶数层right->left
        while (!q.empty())
        {
            currentFloorSize = q.size();
            vector<int> currentFloorEele;
            while (currentFloorSize--)
            {
                // 保存节点数据
                TreeNode *head = q.front();
                q.pop();
                currentFloorEele.emplace_back(head->val);

                // 孩子入队列
                if (head->left)
                    q.emplace(head->left);
                if (head->right)
                    q.emplace(head->right);
            }
            if (flag % 2 == 0)
                reverse(currentFloorEele.begin(), currentFloorEele.end());
            ret.emplace_back(currentFloorEele);
            flag++;
        }
        return ret;
    }
};

// 在每个树行中找最大值
class Solution2
{
public:
    vector<int> largestValues(TreeNode *root)
    {
        if (root == nullptr)
            return {};

        queue<TreeNode *> q;
        q.emplace(root);
        vector<int> ret;

        int currentFloorSize = 0;
        while (!q.empty())
        {
            currentFloorSize = q.size();
            int maxVal = INT_MIN;
            while (currentFloorSize--)
            {
                auto head = q.front();
                q.pop();

                maxVal = max(maxVal, head->val);
                if (head->left)
                    q.emplace(head->left);
                if (head->right)
                    q.emplace(head->right);
            }
            ret.emplace_back(maxVal);
        }
        return ret;
    }
    vector<int> _largestValues(TreeNode *root)
    {
        if (root == nullptr)
            return {};

        queue<TreeNode *> q;
        q.emplace(root);
        vector<int> ret;

        int currentFloorSize = 0;
        while (!q.empty())
        {
            currentFloorSize = q.size();
            priority_queue<int> heap; // 默认是大堆
            while (currentFloorSize--)
            {
                auto head = q.front();
                q.pop();

                heap.emplace(head->val);
                if (head->left)
                    q.emplace(head->left);
                if (head->right)
                    q.emplace(head->right);
            }
            ret.emplace_back(heap.top());
        }
        return ret;
    }
};

// 二叉树最大宽度
class Solution3
{
public:
    int widthOfBinaryTree(TreeNode *root)
    {
        vector<pair<TreeNode *, unsigned int>> LevelSize; // 模拟队列，将二叉树以顺序结构存储
        unsigned int ret = 0;                             // 统计结果
        LevelSize.emplace_back(root, 0);

        while (!LevelSize.empty())
        {
            // 取出该层的首尾节点，并更新结果
            auto &[x1, y1] = LevelSize[0];
            auto &[x2, y2] = LevelSize.back();
            ret = max(ret, y2 - y1 + 1);

            // 让孩子入队
            vector<pair<TreeNode *, unsigned int>> tmp; // 临时存储下一层的节点，最后覆盖原队列
            for (auto &[x, y] : LevelSize)
            {
                if (x->left)
                    tmp.emplace_back(x->left, y * 2 + 1);
                if (x->right)
                    tmp.emplace_back(x->right, y * 2 + 2);
            }

            // 更新层
            LevelSize = tmp;
        }
        return ret;
    }
};

// 最后一块石头的重量
class Solution4
{
public:
    int lastStoneWeight(vector<int> &stones)
    {
        priority_queue<int> MaxHeap;
        for (int x : stones)
            MaxHeap.emplace(x);
        while (MaxHeap.size() > 1)
        {
            int max = MaxHeap.top();
            MaxHeap.pop();
            int next = MaxHeap.top();
            MaxHeap.pop();
            if (max > next)
                MaxHeap.emplace(max - next);
        }

        return MaxHeap.size() ? MaxHeap.top() : 0;

        // priority_queue<int> max_heap;
        // for(int& x : stones)
        //     max_heap.emplace(x);
        //
        // int max = 0;
        // int next = 0;
        // while(!max_heap.empty())
        //{
        //    if(max_heap.size() == 1)
        //        break;
        //
        //    max = max_heap.top();
        //    max_heap.pop();
        //    next = max_heap.top();
        //    max_heap.pop();
        //
        //    if(max != next)
        //        max_heap.emplace(max-next);
        //}
        // if(max_heap.empty())
        //    return 0;
        // return max_heap.top();
    }
};

// 数据流中的第k大元素
class KthLargest
{
public:
    KthLargest(int k, vector<int> &nums)
        : _k(k)
    {
        for (int x : nums)
        {
            _minHeap.emplace(x);
            if (_minHeap.size() > k)
                _minHeap.pop();
        }
    }

    int add(int val)
    {
        _minHeap.emplace(val);
        if (_minHeap.size() > _k)
            _minHeap.pop();
        return _minHeap.top();
    }

private:
    priority_queue<int, vector<int>, greater<int>> _minHeap;
    int _k;
};

// 前k个高频单词
class Solution5
{
public:
    vector<string> topKFrequent(vector<string> &words, int k)
    {
        // 1.统计每一个单词出现的次数
        unordered_map<string, int> hash;
        for (string &s : words)
            hash[s]++;

        // 2.将单词以及它出现的次数插入到大小为k的小堆中
        // 同时设置比较函数，利用次数来比较, 如果次数相等，则比较字典序
        auto cmp = [](const pair<string, int> &a, const pair<string, int> &b)
        {
            return a.second == b.second ? a.first < b.first : a.second > b.second;
        };

        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> minHeap(cmp);
        for (auto &x : hash)
        {
            minHeap.emplace(x);
            if (minHeap.size() > k)
            {
                // 这里为什么可以直接将堆顶数据删除，而不与待插入的数据比较?
                // 因为如果进入到这个判断里，说明此时已经多了一个元素，而堆顶的元素是最小的，不可能是结果，直接删除即可。
                minHeap.pop();
            }
        }

        // 3.将小堆中的数据重新存储
        vector<string> ret(k);
        for (int i = k - 1; i >= 0; i--)
        {
            ret[i] = minHeap.top().first;
            minHeap.pop();
        }

        return ret;
    }
};

// 数据流的中位数
class MedianFinder
{
public:
    MedianFinder()
    {
    }

    void addNum(int num)
    {
        if (_maxHeap.size() == _minHeap.size())
        {
            if (_maxHeap.size() == 0 || num <= _maxHeap.top())
                _maxHeap.emplace(num);
            else
            {
                _minHeap.emplace(num);
                _maxHeap.emplace(_minHeap.top());
                _minHeap.pop();
            }
        }
        else
        {
            if (num > _maxHeap.top())
                _minHeap.emplace(num);
            else
            {
                _maxHeap.emplace(num);
                _minHeap.emplace(_maxHeap.top());
                _maxHeap.pop();
            }
        }
    }

    double findMedian()
    {
        if (!_maxHeap.empty() || !_minHeap.empty())
        {
            if (_maxHeap.size() == _minHeap.size())
                return (_maxHeap.top() + _minHeap.top()) / 2.0;
            else
                return _maxHeap.top();
        }
        return 0;
    }

private:
    priority_queue<int> _maxHeap;
    priority_queue<int, vector<int>, greater<int>> _minHeap;
};

int main()
{

    return 0;
}